1541. Сумма степеней

В этой задаче Вам необходимо найти сумму степеней:

S(l, h, k) = l^k + (l + 1)^k + (l + 2)^k + … + (h – 1)^k + h^k

По заданным l, h и k Вам следует найти S(l, h, k).

Вход. Содержит не более 9999 тестов. Каждый тест содержит три целых числа l, h (0 £ l £ h £ 15000000, |l – h| £ 1000) и k (1 £ k £ 15000000). Последний тест содержит три -1 и не обрабатывается.

Выход. Для каждого теста в отдельной строке вывести его номер в четырех позициях и приблизительное значение S(l, h, k). Это приблизительное значение должно иметь вид 0.ddddddedddddddddd. Мантисса всегда меньше 1 и содержит шесть десятичных знаков. Если мантисса не равна нулю, то первая цифра после десятичной точки должна быть не нулевой. Если значение экспоненты не существенно (не влияет на значение числа), то установить ее равной 1. Формат вывода смотрите в примере.

Пример входа	Пример выхода
1 10 10 10 15 100 -1 -1 -1	Case 0001: 0.149143e0000000011 Case 0002: 0.406971e0000000118

РЕШЕНИЕ

математика

Анализ алгоритма

Представим каждое слагаемое i^k в виде . Например, экспонента числа h^k = равна klgh. Поскольку |l – h| £ 1000, то экспонента остальных степеней не сильно будет отличаться от klgh. Положим exponent = . Поэтому вместо суммирования слагаемых i^k будем суммировать = = . При таком суммировании значение мантиссы не будет слишком большим и для ее нахождения достаточно воспользоваться типом double. Отдельно следует обработать случай, когда искомая сумма равна нулю. Тогда мантиссу следует установить равной нулю, а экспоненту равной 1.

Пример

Рассмотрим второй тест, в котором следует вычислить сумму

10¹⁰⁰ + 11¹⁰⁰ + … + 15¹⁰⁰

Экспонента числа 10¹⁰⁰ равна 100, экспонента числа 15¹⁰⁰ = 10^100lg15 равна 100lg15 ≈ 117,609. Положим exponent = 117. Разделим искомую сумму на 10¹¹⁷ и вычислим ее в переменной типа double:

(10¹⁰⁰ + 11¹⁰⁰ + … + 15¹⁰⁰ ) / 10¹¹⁷ = (10¹⁰⁰ + 10^100lg11 + … + 10^100lg15 ) / 10¹¹⁷ =

10^-17 + 10^-12,861 + … + 10^0,609 ≈ 4,06971

Поскольку полученная сумма не меньше 1, то разделим ее на 10. Получим мантиссу, равную 0,406971. Экспонента при этом увеличится на единицу и станет равной 118.

Реализация алгоритма

Читаем входные данные.

while(scanf("%d %d %d",&l,&h,&k),l + h + k > 0)

{

Обнуляем текущее значение мантиссы s. В целочисленной переменной exponent вычисляем целую часть экспоненты числа h^k = .

s = 0; exponent = k*log10(1.0*h);

Прибавляем к мантиссе s значение для каждого i от l до h.

for(i = l; i <= h; i++)

s += pow(10,k*log10(1.0*i) - exponent);

Если мантисса не меньше 1, то делаем ее таковой.

while (s >= 1) s /= 10, exponent++;

Исключительный случай может возникнуть, когда результат суммы равен 0. Тогда мантисса равна нулю, а значение экспоненты не существенно. Устанавливаем s = 0, exponent = 1

if (!h) s = 0, exponent = 1;

printf("Case %04d: %.6lfe%010d\n", cs++, s, exponent);

}

Java реализация

import java.util.*;

import java.io.*;

public class Main

{

public static void main(String[] args)

throws Exception

{

PrintWriter out = new PrintWriter(System.out,true);

BufferedReader in =

new BufferedReader(new InputStreamReader(System.in));

String stroka;

int cs = 1;

while(!(stroka = in.readLine()).equals("-1 -1 -1"))

{

StringTokenizer st = new StringTokenizer(stroka);

int l = Integer.parseInt(st.nextToken());

int h = Integer.parseInt(st.nextToken());

int k = Integer.parseInt(st.nextToken());

double s = 0;

int exponent = (int) (k * Math.log10(h));

for(int i = l; i <= h; i++)

s += Math.pow(10,k * Math.log10(i) - exponent);

while (s >= 1) { s /= 10; exponent++; }

if (h == 0) { s = 0; exponent = 1;}

out.printf(Locale.US,"Case %04d: %.6fe%010d\n",

cs++, s, exponent);

}

}

}